package dfs;

/**
 * 给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0（表示水域）和 1 （表示陆地）。
 * 一个 岛屿是由 四个方向（水平或者竖直）上相邻的1组成的区域。任何矩阵以外的区域都视为水域。
 *
 * 如果 grid2 的一个岛屿，被 grid1 的一个岛屿完全包含，也就是说 grid2中该岛屿的每一个格子都被 grid1中同一个岛屿完全包含，
 * 那么我们称 grid2中的这个岛屿为子岛屿。
 *
 * 请你返回 grid2 中 子岛屿的 数目。
 *
 * m == grid1.length == grid2.length
 * n == grid1[i].length == grid2[i].length
 * 1 <= m, n <= 500
 * grid1[i][j] 和grid2[i][j]都要么是0要么是1。
 */

public class CountSubIslands_1905 {
    // 同时遍历grid1和grid2，grid2中为1而grid1中为0的岛屿则不是grid1的子岛屿
    public int countSubIslands1(int[][] grid1, int[][] grid2) {
        int m = grid1.length;
        int n = grid1[0].length;
        int res = 0;
        // 将grid2中为1而grid1中为0的岛屿都淹掉
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid1[i][j] == 0 && grid2[i][j] == 1) {
                    dfs1(grid2, i, j, m ,n);
                }
            }
        }

        // grid2剩下的岛屿即为grid1中的子岛屿
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1) {
                    res++;
                    dfs1(grid2, i, j, m ,n);
                }
            }
        }
        return res;
    }

    private void dfs1(int[][] grid, int i, int j, int m, int n) {
        // 边界检测
        if (i >= m || i < 0 || j >= n || j < 0) {
            return;
        }

        // 已经是海水了，尽管在numIslands中已经判断为1，但是递归调用中还是可能为0
        if (grid[i][j] == 0) {
            return;
        }
        // 将已经遍历过的岛屿变成0，这样下次遍历就会直接return
        grid[i][j] = 0;

        // 开始遍历周围的岛屿，将周围的岛屿也变为0
        dfs1(grid, i+1, j, m ,n);
        dfs1(grid, i-1, j, m ,n);
        dfs1(grid, i, j-1, m ,n);
        dfs1(grid, i, j+1, m ,n);
    }

    private boolean notSub;
    // 只遍历一次grid2
    public int countSubIslands2(int[][] grid1, int[][] grid2) {
        int m = grid1.length;
        int n = grid1[0].length;
        int res = 0;
        // 将grid2中为1而grid1中为0的岛屿都淹掉
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1) {
                    notSub = false;
                    dfs2(grid1, grid2, i, j, m, n);
                    if (!notSub) {
                        res++;
                    }

                }
            }
        }
        return res;
    }

    private void dfs2(int[][] grid1, int[][] grid2, int i, int j, int m, int n) {
        // 边界检测
        if (i >= m || i < 0 || j >= n || j < 0) {
            return;
        }

        // 已经是海水了，尽管在numIslands中已经判断为1，但是递归调用中还是可能为0
        if (grid2[i][j] == 0) {
            return;
        }
        // 将已经遍历过的岛屿变成0，这样下次遍历就会直接return
        grid2[i][j] = 0;

        if (grid1[i][j] == 0) {
            notSub = true;
        }

        // 开始遍历周围的岛屿，将周围的岛屿也变为0
        dfs2(grid1, grid2, i + 1, j, m, n);
        dfs2(grid1, grid2, i - 1, j, m, n);
        dfs2(grid1, grid2, i, j - 1, m, n);
        dfs2(grid1, grid2, i, j + 1, m, n);
    }
}
